import copy

grammar5 = {
    "terminals": {"a", "b","c","d","e","#"},  #表示结束
    "non_terminals": {"S'", "S", "A", "B"},
    "start": "S'",
    "productions": [
        ("S'", ["S", "$"]),             #(0) S' :== S#
        ("S", ["a","A","c","B","e"]),   #(1) S :== aAcBe
        ("A", ["b"]),                   #(2) A :== b
        ("A", ["A","b"]),               #(3) A :== Ab
        ("B", ["d"]),                   #(4) B :== d
    ],
}
print(grammar5)
AnalyzerTable = {
    # 状态0
    '0': {'a': 'S2', 
          'c': '', 
          'e': '', 
          'b': '', 
          'd': '', 
          '#': '',
          'S': 'g1',
          'A': '',
          'B': '',
          },
    # 状态1
    '1': {'a': '', 
          'c': '', 
          'e': '', 
          'b': '', 
          'd': '', 
          '#': 'acc',
          'S': '',
          'A': '',
          'B': '',
          },
    # 状态2
    '2':  {'a': '', 
          'c': '', 
          'e': '', 
          'b': 'S4', 
          'd': '', 
          '#': '',
          'S': '',
          'A': 'g3',
          'B': '',
          },
    # 状态3
    '3':  {'a': '', 
          'c': 'S5', 
          'e': '', 
          'b': 'S6', 
          'd': '', 
          '#': '',
          'S': '',
          'A': '',
          'B': '',
          },
    # 状态4
    '4':  {'a': 'r2', 
          'c': 'r2', 
          'e': 'r2', 
          'b': 'r2', 
          'd': 'r2', 
          '#': 'r2',
          'S': '',
          'A': '',
          'B': '',
          },
    # 状态5
    '5':  {'a': '', 
          'c': '', 
          'e': '', 
          'b': '', 
          'd': 'S8', 
          '#': '',
          'S': '',
          'A': '',
          'B': 'g7',
          },
    # 状态6
    '6':  {'a': 'r3', 
          'c': 'r3', 
          'e': 'r3', 
          'b': 'r3', 
          'd': 'r3', 
          '#': 'r3',
          'S': '',
          'A': '',
          'B': '',
          },  
    # 状态7
    '7':  {'a': '', 
          'c': '', 
          'e': 'S9', 
          'b': '', 
          'd': '', 
          '#': '',
          'S': '',
          'A': '',
          'B': '',
          },  
    # 状态8
    '8':  {'a': 'r4', 
          'c': 'r4', 
          'e': 'r4', 
          'b': 'r4', 
          'd': 'r4', 
          '#': 'r4',
          'S': '',
          'A': '',
          'B': '',
          },  
    # 状态9
    '9':  {'a': 'r1', 
          'c': 'r1', 
          'e': 'r1', 
          'b': 'r1', 
          'd': 'r1', 
          '#': 'r1',
          'S': '',
          'A': '',
          'B': '',
          },  
}
print(AnalyzerTable)

# LR0语法分析器
def LR0Analyzer(Grammar, InputStr):
    """
    使用LR(0)分析器分析给定的文法和输入字符串。
    
    Args:
        Grammar (dict): 文法字典，包含非终结符、终结符、产生式等信息。
        InputStr (str): 输入字符串。
    
    Returns:
        bool: 分析结果，True表示接受，False表示拒绝。
    """
    StackState = ['0']  # 状态栈初始状态为0
    StackInput = []  # #输入栈
    print(f"(状态栈：{StackState[-1]},输入符号栈：'')")
    length = len(InputStr)
    i = 0
    while (i < length):
        Chr = InputStr[i] # 获取当前输入字符
        print(f"当前输入：{Chr}")
        TopState = StackState[-1] # 获取栈顶状态
        Action = AnalyzerTable[TopState][Chr]
        if Action == '':  # 如果没有动作，则报错
                print("Error: No such action")
                return False
        elif Action[0] == 'a': # 接受动作
            if i == length - 1: # 如果已经到达输入字符串的末尾，则接受
                print("Accepted")  
                return True 
        elif Action[0] == 'S': # 状态转移动作
            StackState.append(Action[1]) #转移状态
            StackInput.append(Chr) # 将输入字符压入输入栈
            i = i + 1
            print(f"(状态栈：{StackState},输入符号栈：{StackInput})") #栈发生变化后，打印当前状态和输入字符
        elif Action[0] == 'r': # 规约动作
            Production = Grammar["productions"][int(Action[1])]
            ProdLeft = Production[0]# 获取产生式左部                                        
            ProdRight = Production[1] # 获取产生式右部
            for j in range(len(ProdRight)):# 弹出len(ProdRight)个状态和字符
                StackState.pop() 
                StackInput.pop()
                print(f"(状态栈：{StackState},输入符号栈：{StackInput})") #栈发生变化后，打印当前状态和输入字符
            StackInput.append(ProdLeft) # 将产生式左部压入输入栈
            print(f"(状态栈：{StackState},输入符号栈：{StackInput})") #栈发生变化后，打印当前状态和输入字符
            
            # 循环处理状态栈顶的动作，直到没有动作为止            
            TopState = StackState[-1] # 状态发生变化，获取当前状态
            TopSymbol = StackInput[-1]            
            Action = AnalyzerTable[TopState][TopSymbol]  #可能会涉及新的归约或状态转移
            while (Action != '') and ((Action[0] == 'r') or (Action[0] == 'g')):
                if Action[0] == 'r':  # 规约动作
                    Production = Grammar["productions"][int(Action[1])]
                    ProdLeft = Production[0]# 获取产生式左部                                        
                    ProdRight = Production[1] # 获取产生式右部
                    for j in range(len(ProdRight)):# 弹出len(ProdRight)个状态和字符
                        StackState.pop() 
                        StackInput.pop()
                        print(f"(状态栈：{StackState},输入符号栈：{StackInput})") #栈发生变化后，打印当前状态和输入字符
                    StackInput.append(ProdLeft) # 将产生式左部压入输入栈
                elif Action[0] == 'g':  # 状态转移动作
                        StackState.append(Action[1]) #转移状态
                        print(f"(状态栈：{StackState},输入符号栈：{StackInput})") #栈发生变化后，打印当前状态和输入字符
                TopState = StackState[-1] # 状态发生变化，获取当前状态
                TopSymbol = StackInput[-1]
                Action = AnalyzerTable[TopState][TopSymbol]  #重新获取当前状态下的动作
            #endwhile

    #endfor
    return False

print("LR0 Analyzer Testing 1 --------------------------------")
InputString = "abbcde#"
Rst = LR0Analyzer(grammar5, InputString)  
print(f"The syntax of {InputString} is {Rst}")

print("LR0 Analyzer Testing 2 --------------------------------")
InputString = "abccde#"
Rst = LR0Analyzer(grammar5, InputString)  
print(f"The syntax of {InputString} is {Rst}")

